# 5 最长回文子串
# leetcode第5题: https://leetcode.cn/problems/longest-palindromic-substring/description/
# Date: 2024/10/21

def is_P(s: str) -> bool:
    """判断一个字符串是否是回文"""
    length = len(s)
    for i in range(length):
        if s[i] != s[-i - 1]:
            return False
    return True


def longestPalindrome_bf(s: str) -> str:
    """使用暴力求解算法(brute force)"""
    length = len(s)
    if length < 2:
        return s
    result = ""
    max_len = 0
    for i in range(length):
        for j in range(i + 1, length + 1):
            if is_P(s[i:j]) and j - i > max_len:
                result = s[i:j]
                max_len = j - i
    return result


def longestPalindrome_dp(s: str) -> str:
    """利用动态规划(dynamic planning, dp)求解
    回文字本身具有动态转移的性质: 一个回文字符串在去掉两边以后, 剩下的部分仍然是一个回文字
    dp[i][j]: 表示子串s[i:j]是否是一个回文
    dp[i+1][j-1]: 表示去掉头尾之后的子串
    状态转移方程: dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
    边界条件: j - i < 3
    """
    length = len(s)
    if length < 2:
        return s
    # dp = [[False] * length] * length  # 初始化二维数组
    # 由于单个字符串均是回文字, 所以s[i:i+1]必然是回文字, 可以直接在dp中初始化对角线上的元素为True即为初始状态
    # [True None None None None]
    # [None True None None None]
    # [None None True None None]
    # [None None None True None]
    # [None None None None True]
    dp = [[True if i == j else None for i in range(length)] for j in range(length)]
    max_len = 1
    begin = 0
    # 由于二维数组中每个元素的值依赖于靠近对角元素的值, 所以需要修改遍历的顺序
    # 如下面的示例中, 如果要求X的值, 需要依赖Y的值; Y的值则可以通过对角线的上的True来确定.
    # 所以填表的顺序需要沿着对角线的方向一层一层往下求
    # [True None None None None]
    # [None True None None None]
    # [None None True None None]
    # [None Y    None True None]
    # [X    None None None True]
    for window_size in range(2, length + 1):
        for i in range(length):
            j = window_size + i - 1

            if j >= length:  # 如果有边界越界则可以退出当前循环
                break

            if j - i < 3:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

            if dp[i][j] and j - i + 1 > max_len:
                begin = i
                max_len = j - i + 1
    return s[begin:begin + max_len]


def longestPalindrome_opt(s: str) -> str:
    n = len(s)
    dp = [[False] * n for _ in range(n)]

    start = 0
    max_len = 1

    for i in range(n):
        for j in range(i, -1, -1):
            if i == j:
                dp[i][j] = True
            elif j == i - 1 and s[i] == s[j]:
                dp[i][j] = True
            else:
                dp[i][j] = (s[i] == s[j]) and (dp[i - 1][j + 1])
            if dp[i][j] and i - j + 1 > max_len:
                start = j
                max_len = i - j + 1
    return s[start: start + max_len]


if __name__ == "__main__":
    str0 = "ab"
    print(longestPalindrome_dp(str0))
    str1 = "babab"
    print(longestPalindrome_dp(str1))
    str2 = "cbbd"
    print(longestPalindrome_dp(str2))
